U.S. Pat. No. 6,789,222 teaches complete test pattern generation methods for combinational circuits. The methods find all test patterns for all detectable faults for a combinational circuit. This result is accomplished during a single pass through a circuit-level sorted description of a combinational circuit (e.g., a netlist). The methods implement an incremental, breadth-first process that attempts to activate and to propagate faults through the circuit. Input vectors permitting activated faults to reach circuit primary output lines define test patterns.
A sequential circuit can be represented as a combinational part and a separate feedback storage part (prior art FIG. 1). The circuit can be analyzed as an iterative array of the combinational parts, each containing a copy of the fault (prior art FIG. 2; see for example, K-T Cheng, “Tutorial and Survey Paper: Gate-Level Test Generation for Sequential Circuits,” ACM Trans. Design Automation of Electronic Sys., Vol. 1, No. 4, October 1996, Pages 405-442).
The teachings of U.S. Pat. No. 6,789,222 can be applied to such an iterative array for generating test pattern sequences for sequentially detectable faults.
One way to do this is to create an array having a desired number of time-frames and to treat the array as a single, deep, combinational circuit, each time-frame including a copy of the fault. Use a data structure for path-enabling and for fault-propagation functions that is large enough to accommodate the single, deep, combinational circuit. The data structure size must represent a present-state and include one input vector for each time-frame of the array. Perform combinational test pattern generation on the single, deep, combinational circuit, stopping after each subsequent copy of the fault and renaming the subsequent copy with the name of the initial copy, then continuing to the end. This deep-circuit method will find valid, sequentially detectable test sequences for the fault.
Solving the problem this way, however, is impractical and limits the usefulness of the solution to very small sequential circuits and, at most, a few time-frames.
What is needed is a deterministic test pattern generator for sequential circuits that finds test pattern sequences for sequentially detectable faults during a single pass through an iterative array representation of a sequential circuit.
The test pattern generator should use a data structure having size bounded by the size of a data structure used during an initial time-frame.
It should be unnecessary to predict a maximum number of time-frames that may be needed, instead simply proceeding from time-frame to time-frame until a valid test is found or until otherwise terminated.
Finally, for all faults during all subsequent time-frames, the test pattern generator should reuse the path-enabling functions created during the initial time-frame.